package puzzle.projecteuler.p100;

import java.util.Arrays;

import astudy.util.AdvMath;

public class Problem077 {

	/**
	 * 将n表示若干素数之和，最大素数是m的所有方式的个数是f(n,m)
	 * @param args
	 */
	public static void main(String[] args) {

		int n = 2;
		while (true) {
			if (f(n) > 5000) {
				System.out.println(n);
				break;
			}
			n ++;
		}
	}
	
	public static Integer[] ps = AdvMath.primes(1000000);
	
	public static int f(int n, int m) {
		
		if (m <= 1) {
			return 0;
		} else {
			m = p(m);
			if (n == m) {
				return 1;
			} else {
				int s = 0;
				for (int i = 0; i < ps.length; i ++) {
					if (ps[i] <= m) {
						int k = n-m;
						if (k >= 2) {
							s += f(n-m, ps[i]);
						}
					} else {
						break;
					}
				}
				return s;
			}
		}
	}
	
	/**
	 * return the max prime number not more than pm
	 * @param pm
	 * @return
	 */
	public static int p(int pm) {
		int i = Arrays.binarySearch(ps, pm);
		if (i >= 0) {
			return pm;
		} else {
			i = -i-2;
			return ps[i];
		}
	}
	
	public static int f(int n) {
		int s = 0;
		for (int i = 0; i < ps.length; i ++) {
			if (ps[i] <= n) {
				s += f(n, ps[i]);
			} else {
				break;
			}
		}
		return s;
	}
}
